Many of the tasks that are addressed by decision-making systems and artificial intelligence can be framed as constraint satisfaction problems (CSPs). In this framework, the task is specified in terms of a set of variables, each of which can assume values in a given domain, and a set of predicates, or constraints, that the variables must simultaneously satisfy. The set of variables and constraints is referred to as a constraint network. Each constraint may be expressed as a relation, defined over some subset of the variables, denoting valid combinations of their values. A solution to the problem (referred to hereinbelow as a “concrete solution”) is an assignment of a value to each variable from its domain that satisfies all of the constraints. CSP solving techniques were surveyed by Kumar in a paper entitled “Algorithms for Constraint Satisfaction Problems: A Survey,” Artificial Intelligence Magazine 13:1 (1992), pages 32–44.
Constraint satisfaction methods have been found useful in a variety of applications, including:                Artificial intelligence        Robotic control        Temporal reasoning        Natural language parsing        Spatial reasoning        Test-case generation for software and hardware systems        Machine vision        Medical diagnosis        Resource allocation        Crew scheduling        Time tabling        Frequency allocation        Graph coloring.        
For example, Bin et al. describe a constraint satisfaction method for use in automated generation of test programs, in a paper entitled “Using a Constraint Satisfaction Formulation and Solution Techniques for Random Test Program Generation,” IBM Systems Journal 41:3 (2002), pages 386–402. The authors show how random test program generation can be modeled as a CSP, and they describe a set of solution techniques that are used in practical test-case generation tools. Adir et al. describe a test generator that uses a dedicated CSP solver in a paper entitled “Piparazzi: A Test Program Generator for Micro-architecture Flow Verification,” Eighth IEEE International High-Level Design Validation and Test Workshop (Nov. 12–14, 2003), pages 23–28. The test generator converts user requests for micro-architectural events into test programs. Further aspects of the use of CSP solving in automatic test-case generation are described in U.S. Patent Application Publication 2002/0169587 A1.
A number of other constraint satisfaction systems are described in the patent literature. For example, U.S. Pat. No. 5,636,328 describes methods and apparatus for finding values that satisfy a set of constraints, applied particularly to control of a robotic arm. U.S. Pat. No. 5,617,510 describes a method, useful in computer-aided design, of identifying possible solutions to an over-constrained system having a collection of entities and constraints.
The concept of a CSP was generalized by Mittal et al. to cover more complex problems in which variables may be active or inactive, in a paper entitled “Dynamic Constraint Satisfaction Problems,” Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI-90) (Boston, Mass., July 1990), pages 25–32. This generalization is commonly referred to as “Conditional CSP,” or CondCSP. In contrast to the traditional definition of a CSP, a variable in a CondCSP can be either active or inactive. The variable is assigned a value only if it is active. The CondCSP includes compatibility constraints, which specify the set of allowed combinations of values for a set of variables, and activity constraints, which determine whether a given variable is active. A compatibility constraint is active only if all its variables are active. A solution to a CondCSP contains (a) a set of active variables and (b) a value assignment to all the active variables, in which each variable is assigned a value from its domain. The assignment and the set of active variables must satisfy all the activity constraints and all the active compatibility constraints.